#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param nums: A set of numbers
    @return: A list of lists
    """
    def subsets(self, nums):
        self.ret = []
        self.ret.append([])
        self.nums = nums
        self.nums.sort()
        self.len = len(nums)

        # self.loop()
        self.rec_sub(0, [])
        return self.ret

    def loop(self):
        # 针对每个元素: 选择或者不选择, 一直进行下去
        # 但是得出顺序不符合AC的字典序
        for num in self.nums:
            l = len(self.ret)
            for i in range(l):
            # for sub in l:
                sub = self.ret[i]
                self.ret.append(sub + [num])

    def rec_sub(self, begin, sub_path):
        # 深度优先递归
        for i in range(begin, self.len):
            new_sub_path = sub_path + [self.nums[i]]
            self.ret.append(new_sub_path)
            self.rec_sub(i+1, new_sub_path)



def main():
    print("start main")
    s = Solution()
    ret = s.subsets([4, 1, 0])
    print(ret)

if __name__ == "__main__":
    main()
